package dynamicprogramming.除数博弈;
//爱丽丝和鲍勃一起玩游戏，他们轮流行动。爱丽丝先手开局。
//
// 最初，黑板上有一个数字 N 。在每个玩家的回合，玩家需要执行以下操作：
//
//
// 选出任一 x，满足 0 < x < N 且 N % x == 0 。
// 用 N - x 替换黑板上的数字 N 。
//
//
// 如果玩家无法执行这些操作，就会输掉游戏。
//
// 只有在爱丽丝在游戏中取得胜利时才返回 True，否则返回 False。假设两个玩家都以最佳状态参与游戏。
//
//
//
//
//
//
// 示例 1：
//
// 输入：2
//输出：true
//解释：爱丽丝选择 1，鲍勃无法进行操作。
//
//
// 示例 2：
//
// 输入：3
//输出：false
//解释：爱丽丝选择 1，鲍勃也选择 1，然后爱丽丝无法进行操作。
//
//
//
//
// 提示：
//
//
// 1 <= N <= 1000
//
// Related Topics 数学 动态规划
// 👍 283 👎 0
//leetcode submit region begin(Prohibit modification and deletion)
public class Solution {
    //思路：要求N的时候是输是赢，则要看N-K的时候是输是赢，如果N-k输了那么Alice则可以由A到K　，则Alice赢，如果N－K是Alice赢了，则N是Alice输
    //所以动态转移方程为 d[N] = !d[N-K](前提是K是N的因数)
    public boolean divisorGame(int N) {
        if (N==1) return false;
        if (N==2) return true;
        boolean []f = new boolean[N+1];
        f[1] = false;
        f[2] = true ;
        for (int i = 3; i < N+1; i++) {
            f[i] = false;
            //如果在1~i/2之间都没有找到能被i整除的话，超过i/2 的部分也就只有i了，但是规定必须要小于i，所以只需要在1~i/2之间选取
            for (int j = 1; j < i; j++) {
                if (i%j==0&&!f[i-j]){
                    f[i] = true;
                }
            }
        }
        return f[N];
    }

}
//leetcode submit region end(Prohibit modification and deletion)

